package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.ArrayProblem;
import cn.pugle.oj.catalog.BitProblem;
import cn.pugle.oj.catalog.MathProblem;

/**
 * https://leetcode.com/problems/powx-n/
 * https://www.jianshu.com/p/ec0b97676c3e
 * 快速幂
 * <p>
 * see {@link LC372}
 *
 * @author tzp
 * @since 2020/11/3
 */
public class LC50_2 implements ArrayProblem, MathProblem, BitProblem {

    //对n每个为1的bit进行处理, x一直乘上去
    public double myPow(double x, int n) {
        boolean neg = n < 0;
        n = Math.abs(n);
        double ans = 1, base = x;// ans：幂的结果；base：底数a
        int cnt = 0;//debug用
        while (n > 0) {
            if ((n & 1) > 0) {
                ans = ans * base;
            }
            base = base * base;
            n = n >> 1;
            cnt++;//debug用
        }
        System.out.println(cnt);//debug用
        return neg ? 1 / ans : ans;
    }

    public static void main(String[] args) {
//        System.out.println(new LC50().myPow(2, 3));
//        System.out.println(new LC50().myPow(2, 10));
//        System.out.println(new LC50().myPow(2, -2));
        System.out.println(new LC50_2().myPow(0.00001, 2147483647));//艹, 还是超时了
    }
}
